#include <vector>
#include <iostream>
#include <map>
#include <numeric>

using namespace std;

int findSubstringInWraproundString(string p) {
    //使用动态规划
    //dp[i]表示以'a' + i的字母为末尾字母的子字符串的数量!!!! 注意是末尾!!!
    //最多有26个不同的字符，注意s是顺序小写字母
    vector<int> dp(26, 0);
    const int len = p.length();
    int cur = 0;
    for (int i = 0; i < len; ++i) {
        //如果该字符和前一个字符连续，则增加cur。 因为是环状数组，因此我们对26求余
        //这里我们没有减去'a'，是因为我们直接求余了
        if (i > 0 && (p[i-1] + 1) % 26 == p[i] % 26) ++cur;
        else cur = 1;
        //记录该字符为结尾的子字符串的总数。 因为s中严格有序，因此不可能出现一个是ac另一个是ab的情况(即我们不可能漏统计)，都是abcd
        dp[p[i] - 'a'] = max(dp[p[i] - 'a'], cur);
    }
    //最终的结果即为以所有字符为首字符的所有子串的总数
    return accumulate(dp.begin(), dp.end(), 0);
}

// 无法解决s循环问题
int myfindSubstringInWraproundString(string p) {
    int num = 0; map<string, int> mp; string s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
    for(int i = 0; i < p.size(); i++){
        for(int j = 1; j < p.size()-i+1; j++){
            auto it = mp.insert({p.substr(i,j), 1});
            if(it.second){
                if(s.find(p.substr(i,j)) != string::npos) num++;
            }
        }
    }
    return num;
}

int main(){
    string p = "zab";
    cout << findSubstringInWraproundString(p) << endl;
    return 0;
}